'''
需求：使用 python 写出两种常见的快排思想

两种实现思想分析：
核心思想：使用的是分治算法。实现的核心思想则是递归。
  思想1(从小到大排序)：
    1、以开头作为基准数
    2、从两边交替查找，如果找到则进行覆盖
    3、注意：思想1使用的方式是覆盖
    4、最后以基准数作为分割，左右两边分别进行递归调用
  思想2(从小到大排序)：
    1、以结尾作为基准数
    2、定义两个变量，都从开头查找。
    3、如果找到小于基准数的值则进行交换
    4、注意:思想2使用的方式是交换
    5、最后以基准数作为分隔，左右两边分别进行递归调用

注意：思想1 的判断中有一个 <= 和 >= 如果写成 > 和 < 则在有两边的值和基准值相同时会造成死循环
'''



def quick_sort_1(nums):
    return q_sort_1(nums, 0, len(nums) - 1)

def q_sort_1(nums, left, right):
    if left < right:
        pivot = partition(nums,left,right)

        q_sort_1(nums, left, pivot - 1)
        q_sort_1(nums, pivot + 1, right)

    return nums

# 思想1的具体实现
# def partition(nums, left, right):
#     pivotkey = nums[left]

#     while left < right :
#         while left < right and nums[right] >= pivotkey :
#             right -= 1
#         nums[left] = nums[right]

#         while left < right and nums[left] <= pivotkey :
#             left += 1
#         nums[right] = nums[left]

#     nums[left] = pivotkey
#     return left 


# 思想二的具体体现
def partition(nums, left, right):
    pivotkey = nums[right]
    i = left

    for j in range(left,right):
        if nums[j] < pivotkey:
            nums[i],nums[j] = nums[j],nums[i]
            i += 1
    nums[i],nums[right] = nums[right],nums[i]
    return i


# test
# test = [121, 144, 19, 161, 19, 144, 19, 11]  
test = [9,4,8,11,34,80,100,21,1,2,3,5,11,32,44]
quick_sort_1(test)
print(test)


